package demo4;

import java.util.List;

/**
 * 派对的最大快乐值 员工信息的定义如下: class Employee { public int happy;
 * 这名员工可以带来的快乐值 List<Employee> subordinates;
 * 这名员工有哪些直接下级 } 公司的每个员工都符合 Employee 类的描述。
 * 整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树
 * 树的头节点是公司唯一的老板，除老板之外的每个员工都有唯一的直接上级
 * 叶节点是没有任何下属的基层员工(subordinates列表为空)，
 * 除基层员工外每个员工都有一个或多个直接下级 这个公司现在要办party，
 * 你可以决定哪些员工来，哪些员工不来，规则：
 * 1.如果某个员工来了，那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累加
 * 3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
 */

public class TestDemo1 {
    static class Employee{
        public int happy;//快乐值
        public List<Employee> next;//所有的下级
    }

    public static class Info{
        public int yes;//员工来的收益
        public int no;//员工不来的收益
        public Info(int yes,int no){
            this.yes = yes;
            this.no = no;
        }
    }

    public static Info process(Employee head){
        if(head == null) return new Info(0,0);
        int yes = head.happy;//x节点已经确定来了
        int no = 0;
        //遍历每一个子树
        for(Employee x : head.next){
            //给我下一层孩子的信息
            Info child = process(x);
            //如果我不来,最大happy值就是 我下级来或者不来的最大值
            no += Math.max(child.yes,child.no);
            yes += child.no;//只要我来就不让我的下级来,所以加上下级不来的收益
        }
        return new Info(yes,no);
    }


    public static int maxHappy(Employee head){
        if(head==null) return  0;
        return Math.max(process(head).no,process(head).yes);
    }





}
